/*      > C.Deque - Deque data type */

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include "deque.h"

#ifdef test
#include <stdio.h>
#endif

struct link
{
        struct link *next;
        char data[1];
};

typedef struct link *link;

/* Return values from functions */

#define OK      1
#define ERR     0

/* General component routines */

deque deq_new (int obj_len)
{
        register deque d;

        d = malloc(sizeof(struct deque));

        if ( d == NULL )
                return NULL;

        d->head     = NULL;
        d->tail     = NULL;
        d->obj_size = obj_len;

        return d;
}

void deq_free (deque d)
{
        deq_clear(d);
        free(d);
}

void deq_clear (deque d)
{
        link this_entry = d->head;
        link next_entry;
        
        while ( this_entry != NULL )
        {
                next_entry = this_entry->next;
                free(this_entry);
                this_entry = next_entry;
        }

        d->head = d->tail = NULL;
}

int deq_copy (deque d1, const deque d2)
{
        link p;
        link new;
        link last;
        int size;

        if ( d1->obj_size != d2->obj_size )
                return ERR;

        deq_clear(d1);

        last = (link)d1;
        size = d2->obj_size;

        for ( p = d2->head; p != NULL; p = p->next )
        {
                new = malloc(sizeof(struct link) - 1 + size);
                if ( new == NULL )
                {
                        deq_clear(d1);
                        return ERR;
                }
                last->next = new;
                memcpy(new->data,p->data,size);
                last = new;
        }

        last->next = NULL;
        d1->tail = last;

        return OK;
}

int deq_equal (const deque d1, const deque d2)
{
        int size;
        link p1;
        link p2;

        if ( d1->obj_size != d2->obj_size )
                return 0;

        size = d1->obj_size;

        for
        (
                p1 = d1->head, p2 = d2->head;
                p1 != NULL && p2 != NULL;
                p1 = p1->next, p2 = p2->next
        )
        {
                if ( memcmp(p1->data,p2->data,size) != 0 )
                        return 0;
        }

        return ( p1 == p2 );
}

int deq_empty (const deque d)
{
        return ( d->head == NULL );
}

int deq_size (const deque d)
{
        int i = 0;
        link p;

        for ( p = d->head; p != NULL; p = p->next )
                ++i;

        return i;
}

int deq_iterate (const deque d, int (*process)(void *))
{
        int ret = 0;
        link p;

        for ( p = d->head; p != NULL; p = p->next )
        {
                ret = (*process)(p->data);

                /* Non-zero => stop processing here */

                if ( ret != 0 )
                        break;
        }

        /* Negative => Abnormal (error) termination */

        return ( ret >= 0 );
}

/* deque-specific routines */

int deq_add (deque d, int pos, const void *object)
{
        link new;

        new = malloc(sizeof(struct link) - 1 + d->obj_size);

        if ( new == NULL )
                return ERR;

        memcpy(new->data,object,d->obj_size);

        if ( pos == Front )
        {
                new->next = d->head;
                d->head = new;
                if ( d->tail == NULL )
                        d->tail = d->head;
        }

        else
        {
                new->next = NULL;
                if ( d->tail != NULL )
                        ((link)d->tail)->next = new;
                d->tail = new;
                if ( d->head == NULL )
                        d->head = d->tail;
        }

        return OK;
}

int deq_pop (deque d, int pos)
{
        link p;

        if ( d->head == NULL )
                return ERR;

        else if ( d->head == d->tail )
        {
                free(d->head);
                d->head = d->tail = NULL;
        }

        else if ( pos == Front )
        {
                p = d->head;
                d->head = p->next;
                free(p);
        }

        else
        {
                p = d->head;
                while ( p->next != (link)d->tail )
                        p = p->next;
                p->next = NULL;
                free(d->tail);
                d->tail = p;
        }

        return OK;
}

void *deq_front (const deque d)
{
        if ( d->head == NULL )
                return NULL;

        return ((link)d->head)->data;
}

void *deq_back (const deque d)
{
        if ( d->tail == NULL )
                return NULL;

        return ((link)d->tail)->data;
}

/*---------------------------------------------------------------------------*/

#ifdef test
int print (void *ptr)
{
        printf("%d ",*(int *)ptr);
        return STATUS_CONTINUE;
}

void deq_dump (deque d)
{
        printf("deque: ");
        deq_iterate(d,print);
        putchar('\n');
}
#endif

/*---------------------------------------------------------------------------*/

#ifdef test

#define BUFLEN 255

int main (void)
{
        char buf[BUFLEN], str[BUFLEN];
        int i, j, num;
        deque d[10];

        for ( i = 0; i < 10; ++i )
                d[i] = deq_new(sizeof(int));

        for ( ; ; )
        {
                printf(">");
                fgets(buf,BUFLEN,stdin);

                if ( buf[0] == '\n' || buf[0] == '\0' )
                        continue;
                else if ( sscanf(buf,"clear %1d",&i) == 1 )
                        deq_clear(d[i]);
                else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
                        deq_copy(d[i],d[j]);
                else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
                        printf("%s\n",(deq_equal(d[i],d[j]) ? "yes" : "no"));
                else if ( sscanf(buf,"empty %1d",&i) == 1 )
                        printf("%s\n",(deq_empty(d[i]) ? "yes" : "no"));
                else if ( sscanf(buf,"size %1d",&i) == 1 )
                        printf("%d\n",deq_size(d[i]));
                else if ( sscanf(buf,"dump %1d",&i) == 1 )
                        deq_dump(d[i]);
                else if ( sscanf(buf,"add %1d %s %d",&i,str,&num) == 3 )
                        deq_add(d[i],(str[0]=='f'),&num);
                else if ( sscanf(buf,"pop %1d %s",&i,str) == 2 )
                        deq_pop(d[i],(str[0]=='f'));
                else if ( sscanf(buf,"front %1d",&i) == 1 )
                {
                        int *p = deq_front(d[i]);
                        if ( p == NULL )
                                printf("Empty\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( sscanf(buf,"back %1d",&i) == 1 )
                {
                        int *p = deq_back(d[i]);
                        if ( p == NULL )
                                printf("Empty\n");
                        else
                                printf("%d\n",*p);
                }
                else if ( strncmp(buf,"quit",4) == 0 )
                        break;
                else
                        printf("Mistake\n");
        }

        printf("Deleting d[0-9]\n");
        for ( i = 0; i < 10; ++i )
                deq_free(d[i]);

        return 0;
}

#endif
